// https://www.lintcode.com/problem/positions-of-large-groups/

public class Solution {
    /**
     * @param S: a string
     * @return: the starting and ending positions of every large group
     */
    public List<List<Integer>> largeGroupPositions(String S) {
        // Write your code here
        List<List<Integer>> ret = new ArrayList<>();
        List<List<Integer>> count = new ArrayList<>();
        count.add(new ArrayList<Integer>());
        count.get(0).add(0);
        count.get(0).add(0);
        Character prev = S.charAt(0);
        for (int i = 1; i < S.length(); ++i) {
            Character c = S.charAt(i);
            if (c == prev) {
                List<Integer> p = count.get(count.size() - 1);
                p.set(1, i);
            } else {
                prev = c;
                count.add(new ArrayList<Integer>());
                count.get(count.size() - 1).add(i);
                count.get(count.size() - 1).add(i);
            }
        }
        for (List<Integer> p : count) {
            if ((p.get(1) - p.get(0)) >= 2) {
                ret.add(p);
            }
        }
        return ret;
    }
}